#include <cstdio>
#include <algorithm>
#include <iostream>
#define LL long long
#define IN inline
#define re register
using namespace std;
IN int read() {
	int res = 0; char ch = getchar();
	for(; !isdigit(ch); ch = getchar());
	for(; isdigit(ch); ch = getchar()) res = (res << 3) + (res << 1) + (ch ^ 48);
	return res;
}
int n, q, p[10000];
struct Node{
	int val, rk, id;
}a[10000];
bool cmp1(Node x, Node y) {return (x.val == y.val) ? (x.id < y.id) : (x.val < y.val);}
bool cmp2(Node x, Node y) {return x.id < y.id;}
bool check(int x, int y, int z) {return (a[p[x]].val == y) ? (a[p[x]].id > z) : (a[p[x]].val > y);}
int pp[10000];
void modify(int x, int y) {
	if(y == a[x].val) return ;
	int l = 0, r = n, mid, ans;
//	if(y < a[x].val) l = 1, r = a[x].rk - 1, ans = a[x].rk;
//	else l = a[x].rk + 1, r = n, ans = a[x].rk;
//	printf("CHECK(%d %d %d) = %d\n",252,y,220,check(252, y, 220));
	for(; l <= r; ) {
		mid = l + r >> 1;
//		printf("CHECK(%d %d %d) = %d\n",mid,y,x,check(mid, y, x));
		if(check(mid, y, x)) ans = mid, r = mid - 1;
		else l = mid + 1;
	}
		--ans;
//	cout << endl;
	for(int i = 1; i <= n; ++i)
		pp[i] = p[i];
//	printf("CH %d %d\n",a[x].rk,ans);
	if(ans < a[x].rk) {
		for(int i = a[x].rk - 1; i >= ans; --i) {
			a[pp[i]].rk ++;
			p[i + 1] = pp[i];
		}
	}
	else {
		for(int i = a[x].rk + 1; i <= ans; ++i) {
			a[pp[i]].rk --;
			p[i - 1] = pp[i];
		}
	}
	a[x].rk = ans, p[ans] = x,
	a[x].val = y;
//	cout << endl;
//	for(int i = 1; i <= n; ++i)
//		pp[i] = p[i], printf("%d ",p[i]);
//	printf("CH %d %d\n",a[x].rk,ans);
	return ;
}
void out() {
	cout << endl;
	for(int i = 1; i <= n; ++i)
		printf("%d %d %d\n",a[i].id,a[i].val,a[i].rk);
	cout << endl;
	return ;
}
int main() {
	freopen("sort.in","r",stdin);
	freopen("sort.out","w",stdout);
	n = read(), q = read();
	for(int i = 1; i <= n; ++i)
		a[i].val = read(), a[i].id = i;
	sort(a + 1, a + n + 1, cmp1);
	for(int i = 1; i <= n; ++i)
		a[i].rk = i;
	sort(a + 1, a + n + 1, cmp2);
	for(int i = 1; i <= n; ++i)
		p[a[i].rk] = i;
	int x, y, type;
//	out();
	for(int i = 1; i <= q; ++i) {
		type = read();
		if(type == 1) 
			x = read(), y = read(),
			modify(x, y);
		else 
			x = read(), 
			printf("%d\n",a[x].rk);
	}
	return 0;
}
